The importance of error correction coding of data in digital computer systems has increased greatly as the density of the data recorded on mass storage media, more particularly magnetic disks, has increased. With higher recording densities, a tiny imperfection in the recording surface of a disk can corrupt a large amount of data. In order to avoid losing that data, error correction codes ("ECC's") are employed to, as the name implies, correct the erroneous data.
Before a string of data symbols is recorded on a disk, it is mathematically encoded to form ECC symbols. The ECC symbols are then appended to the data string to form code words--data symbols plus ECC symbols--and the code words are then stored on the disk. When the stored data is to be accessed from the disk, the code words containing the data symbols are retrieved from the disk and mathematically decoded. During decoding any errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [For a detailed description of decoding see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972].
Stored digital code words can contain multiple errors. One of the most effective types of ECC used for the correction of multiple errors is a Reed-Solomon code [For a detailed description of Reed-Solomon codes, see Peterson and Weldon, Error Correction Codes]. Error detection and correction techniques for Reed-Solomon ECC's are well known. Id. One such technique begins with again encoding the code word data to generate a new set of ECC symbols and then comparing this set of ECC symbols with the ECC symbols in the retrieved code word, i.e. the set of ECC symbols generated by the pre-storage encoding of the data, to detect any errors in the retrieved data. [For a detailed discussion of this error detection technique, see U.S. Pat. No. 4,413,339 issued to Riggle and Weng].
With this technique, the two sets of ECC symbols may be compared by exclusive OR'ing the corresponding symbols of each set. The resulting symbols, which are "residue"symbols, are then used to determine the locations and/or values of the errors. If all errors are found to occur within an n-k, or "r", symbol grouping of code word symbols, that is, within a "window" or r consecutive symbols, a relatively straight-forward forward decoding technique known as error trapping decoding may be used to correct them. Error trapping decoding corrects, for an (n,k) code, up to (n-1)/k errors per code word. The errors must all occur within an r-symbol window, however, such error patterns are the most common. This technique is most effective for low rate codes, that is, codes which encode a large number of data symbols into a small number of redundancy symbols (r&lt;&lt;k).
The error trapping decoding technique starts with a counting of the non-zero residue symbols. If there are fewer than T non-zero symbols, where T is less than one-half the "distance" of the error correction code, it is assumed that the data symbols are error-free and the errors are in the redundancy symbols. Thus no error correction is required.
If there are more than T non-zero symbols, the residue symbols are manipulated in accordance with the same (n,k) error correction code used to encode the data symbols. This may be accomplished by loading the residue symbols into an encoder used to encode the data, and shifting the encoder with no serial input thereto. For each manipulation cycle, that is, each clocking of the encoder or each software iteration, a count of the non-zero (manipulated) residue symbols is taken. If the count is less than T, the manipulated symbols are combined with the code word symbols to correct them. If the count is greater than T, another manipulation cycle and counting operation are performed.
While error trapping decoding is a straight-forward error correction technique which is easily implemented, it is relatively slow. It involves repeatedly cycling an encoder and performing a time consuming counting operation, up to n times per code word. Thus error trapping decoding may be too slow for systems with high data transfer rates. Accordingly, a fast error trapping decoding technique is highly desirable.